En
teoría de la complejidad computacional, la
clase de complejidad NL (espacio logarítmico no determinista) es el conjunto de los
problemas de decisión que pueden ser resueltos en espacio
log(n) (sin contar el tamaño de la entrada), donde
n es el tamaño de la entrada, por una
máquina de Turing no determinista tal que la solución si existe es única. La clase
L está contenida en
NL y está contenida estrictamente en
PSPACE. Como
NL también está contenida estrictamente en PSPACE, se concluye que en la relación
P es diferente de
NP o bien
NP es diferente de
PSPACE, pero no se sabe cual de las dos inclusiones es propia.